|
In computational linguistics, the term mildly context-sensitive grammar formalisms refers to several grammar formalisms that have been developed with the ambition to provide adequate descriptions of the syntactic structure of natural language. Every mildly context-sensitive grammar formalism defines a class of mildly context-sensitive grammars (the grammars that can be specified in the formalism), and therefore also a class of mildly context-sensitive languages (the formal languages generated by the grammars). == Background == By 1985, several researchers in descriptive and mathematical linguistics had provided evidence against the hypothesis that the syntactic structure of natural language can be adequately described by context-free grammars.〔Riny Huybregts. The Weak Inadequacy of Context-Free Phrase Structure Grammars. In Ger de Haan, Mieke Trommelen, and Wim Zonneveld, editors, ''Van periferie naar kern'', pages 81–99. Foris, Dordrecht, The Netherlands, 1984.〕〔Stuart M. Shieber. Evidence Against the Context-Freeness of Natural Language. ''Linguistics and Philosophy'', 8(3):333–343, 1985.〕 At the same time, the step to the next level of the Chomsky hierarchy, to context-sensitive grammars, appeared both unnecessary and undesirable. In an attempt to pinpoint the exact formal power required for the adequate description of natural language syntax, Aravind Joshi characterized ‘grammars (and associated languages) that are only slightly more powerful than context-free grammars (context-free languages)’.〔Aravind K. Joshi. Tree Adjoining Grammars: How Much Context-Sensitivity Is Required to Provide Reasonable Structural Descriptions?. In David R. Dowty, Lauri Karttunen, and Arnold M. Zwicky, editors, ''Natural Language Parsing'', pages 206–250. Cambridge University Press, 1985.〕 He called these grammars ''mildly context-sensitive grammars'' and the associated languages ''mildly context-sensitive languages''. Joshi’s characterization of mildly context-sensitive grammars was biased toward his work on tree-adjoining grammar (TAG). However, together with his students Vijay Shanker and David Weir, Joshi soon discovered that TAGs are equivalent, in terms of the generated string languages, to the independently introduced head grammar (HG).〔David J. Weir, K. Vijay-Shanker, and Aravind K. Joshi. The Relationship Between Tree Adjoining Grammars and Head Grammars. In ''Proceedings of the 24th Annual Meeting of the Association for Computational Linguistics (ACL)'', pages 67–74, New York, USA, 1986.〕 This was followed by two similar equivalence results, for linear indexed grammar (LIG)〔K. Vijay-Shanker. A Study of Tree Adjoining Grammars. Ph.D. thesis, University of Pennsylvania, Philadelphia, USA, 1987.〕 and combinatory categorial grammar (CCG),〔David J. Weir and Aravind K. Joshi. Combinatory Categorial Grammars: Generative Power and Relationship to Linear Context-Free Rewriting Systems. In ''Proceedings of the 26th Annual Meeting of the Association for Computational Linguistics (ACL)'', pages 278–285, Buffalo, USA, 1988.〕 which showed that the notion of mildly context-sensitivity is a very general one and not tied to a specific formalism. The TAG-equivalent formalisms were generalized by the introduction of linear context-free rewriting systems (LCFRS).〔K. Vijay-Shanker, David J. Weir, and Aravind K. Joshi. Characterizing Structural Descriptions Produced by Various Grammatical Formalisms. In ''Proceedings of the 25th Annual Meeting of the Association for Computational Linguistics (ACL)'', pages 104–111, Stanford, CA, USA, 1987.〕〔David J. Weir. Characterizing Mildly Context-Sensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylvania, Philadelphia, USA, 1988.〕 These grammars define an infinite hierarchy of string languages in between the context-free and the context-sensitive languages, with the languages generated by the TAG-equivalent formalisms at the lower end of the hierarchy. Independently of and almost simultaneously to LCFRS, Hiroyuki Seki et al. proposed the essentially identical formalism of multiple context-free grammar (MCFG).〔Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii, and Tadao Kasami. On Multiple Context-Free Grammars. ''Theoretical Computer Science'', 88(2):191–229, 1991.〕 LCFRS/MCFG is sometimes regarded as the most general formalism for specifying mildly context-sensitive grammars. However, several authors have noted that some of the characteristic properties of the TAG-equivalent formalisms are not preserved by LCFRS/MCFG,〔Makoto Kanazawa. The Pumping Lemma for Well-Nested Multiple Context-Free Languages. In ''Developments in Language Theory. 13th International Conference, DLT 2009, Stuttgart, Germany, June 30–July 3, 2009. Proceedings'', volume 5583 of ''Lecture Notes in Computer Science'', pages 312–325, 2009.〕 and that there are languages that have the characteristic properties of mildly context-sensitivity but are not generated by LCFRS/MCFG.〔Laura Kallmeyer. On Mildly Context-Sensitive Non-Linear Rewriting. ''Research on Language and Computation'', 8(4):341–363, 2010.〕 Recent years have seen increased interest in the restricted class of ''well-nested'' linear context-free rewriting systems/multiple context-free grammars,〔〔Carlos Gómez-Rodríguez, Marco Kuhlmann, and Giorgio Satta. Efficient Parsing of Well-Nested Linear Context-Free Rewriting Systems. In ''Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL)'', pages 276–284, Los Angeles, USA, 2010.〕 which define a class of grammars that properly includes the TAG-equivalent formalisms but is properly included in the unrestricted LCFRS/MCFG hierarchy. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Mildly context-sensitive grammar formalism」の詳細全文を読む スポンサード リンク
|